#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int
gcd(const int a, const int b)
{
	if (a == 0)
		return b;

	return gcd(b % a, a);
}

int
extended_gcd(int a, int b, int *x, int *y)
{
	int x1, y1;
	int d;

	if (a == 0) {
		*x = 0;
		*y = 1;
		return b;
	}

	d = extended_gcd(b % a, a, &x1, &y1);
	*x = y1 - (b / a) * x1;
	*y = x1;
	return d;
}

int
main(int argc, char **argv)
{
	;
}
